package chapter2;

/**
 * 删除单链表和双链表的倒数第K个节点
 */
public class RemoveLastKthNode {
    /**
     * 删除单链表的倒数第K个节点，不使用快慢指针的方法
     * 先遍历一遍链表，判断k-n的3种情况，或者直接推出删除正数第几个节点
     * 这里是判断k-n的3种情况
     * @param head
     * @return
     */
    public ListNode removeLastKthNode(ListNode head, int k) {
        if (head == null || k < 1) {
            return head;
        }
        ListNode current = head;
        // 求k-n
        while (current != null) {
            k--;
            current = current.next;
        }

        if (k == 0) {
            head = head.next;
        }

        if (k < 0) {
            current = head;
            while (++k != 0) {
                current = current.next;
            }
            current.next = current.next.next;
        }
        return head;
    }

    /**
     * 删除单链表的倒数第k个节点，使用快慢指针,只需遍历一遍（推荐）
     * @param head
     * @param k
     * @return
     */
    public ListNode removeLastKthNode2(ListNode head, int k) {
        if (head == null || k < 1) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode fast = dummy;// 必须从dummy开始，快指针先走k+1步
        ListNode slow = dummy;// 必须从dummy开始(比如倒数k=n)
        int id = 0;
        // 快指针先走k+1步
        while (fast != null && id <= k) {
            id++;
            fast = fast.next;
        }

        // 若fast指向null，说明已经遍历完链表,id = n+1，若id != k+1，说明k > n,则直接返回head
        if (fast == null && id < k + 1) return head;

        // 使fast指向null,slow指向倒数第k+1个节点
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }

        slow.next = slow.next.next; // 删除倒数第k个节点
        return dummy.next;
    }

    /**
     * 删除双向链表的倒数第k个节点，使用快慢指针
     * 需要注意删除节点的下一个节点的连接问题
     * @param head
     * @param k
     * @return
     */
    public DoubleNode removeLastKthNode(DoubleNode head, int k) {
        if (head == null || k < 1) return head;
        DoubleNode dummy = new DoubleNode(0);
        dummy.next = head;
        DoubleNode fast = dummy;
        DoubleNode slow = dummy;
        int id = 0;
        // 快指针先走k+1步
        while (fast != null && id <= k) {
            id++;
            fast = fast.next;
        }

        // 若fast指向null，说明已经遍历完链表,id = n+1，若id != k+1，说明k > n,则直接返回head
        if (fast == null && id < k + 1) {
            return head;
        }

        // fast == null, id = k+1,说明k==n,删除第一个节点
        if (fast == null && id == k + 1) {
            slow.next = slow.next.next; // 删除倒数第1个节点
            slow.next.last = null;
        }

        // 使fast指向null,slow指向倒数第k+1个节点
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        // 如何删除的不是倒数第1个节点
        if (slow.next.next != null)
            slow.next.next.last = slow;

        slow.next = slow.next.next; // 删除倒数第k个节点

        return dummy.next;
    }

}
